package my.algo.tree;

import java.util.LinkedList;

/**
 * 二叉查找（排序）树（BST）
 * 1. 若左子树非空，则左子树所有节点小于根节点。
 * 2. 若右子树非空，则右子树所有节点大于根节点。
 * 3. 左右子树本身也是一颗二叉查找树。
 * 根据遍历序列确定二叉树：
 *      先序遍历根在前部，后序遍历根在尾部，中序根在中间，左边是左子数，右边是右子树。
 * @author fengbo
 * @date 2018/8/6
 */
public class BinarySearchTree<T extends Comparable<T>> {

    private Node root;

    public int size() {
        return size(root);
    }

    public int size(Node x) {
        if (x == null) {
            return 0;
        } else {
            return x.n;
        }
    }

    public T get(T value) {
        return get(root, value);
    }

    private T get(Node x, T value) {
        if (x == null) {
            return null;
        }
        int cmp = value.compareTo(x.value);
        if (cmp < 0) {
            return get(x.left, value);
        } else if (cmp > 0) {
            return get(x.right, value);
        } else {
            return x.value;
        }
    }

    private void put(T value) {
        root = put(root, value);
    }

    private Node put(Node x, T value) {
        if (x == null) {
            return new Node(value, 1);
        }
        int cmp = value.compareTo(x.value);
        if (cmp < 0 ) {
            x.left = put(x.left, value);
        } else if (cmp > 0) {
            x.right = put(x.right, value);
        }
        x.n = size(x.left) + size(x.right) + 1;
        return x;
    }

    public void delete(T key) {
        delete(root, key);
    }

    private Node delete(Node node, T key) {
        if (node == null) {
            return null;
        }
        int cmp = key.compareTo(node.value);
        if (cmp < 0) {
            node.left = delete(node.left, key);
        } else if (cmp > 0) {
            node.right = delete(node.right, key);
        } else {
            // 如果左右都为空，返回空
            // 如果右节点或者左节点为空，返回不为空的节点作为被删除节点父节点的子节点
            // 就是说使用不为空的那个子节点替换该节点
            if (node.right == null) {
                return node.left;
            }
            if (node.left == null) {
                return node.right;
            }
            // 如果左右都不为空，选取右子树的最小节点替换该节点，就是右子树的左子树的第一个左节点为空的节点
            // 该节点大于被删除的节点，所以该节点大于被删除节点的左子树上所有节点，小于被删除节点右子树上其它节点
            Node x = node;
            node = min(x.right);
            // 重新构建该节点，因为该节点左子树为空，并大于被删除节点左子树上所有节点，所以该节点左子树等于被删除节点的左子树即可
            // 右子树的构建等同于将被删除节点的右子树赋给该节点，然后在该节点的右子树中删除该节点
            node.right = resizeRight(x.right);
            node.left = x.left;
        }
        node.n = size(node.left) + size(node.right) + 1;
        return node;
    }

    private Node resizeRight(Node node) {
        if (node.left == null) {
            return node.right;
        }
        node.left = resizeRight(node.left);
        node.n = size(node.left) + size(node.right) + 1;
        return node;
    }

    private Node min(Node node) {
        if (node.left == null) {
            return node;
        }
        return min(node.left);
    }

    private class Node {
        private T value;
        private Node left, right;
        private int n;
        Node(T value, int n) {
            this.value = value;
            this.n = n;
        }
    }

    /**
     * 递归遍历
     */
    public void recursiveTraversal() {
        recursiveTraversal(root);
    }

    private void recursiveTraversal(Node node) {
        if (node != null) {
            // 先序遍历：遍历顺序规则为【根左右】 40 20 10 30 60 50 70
            // 中序遍历：遍历顺序规则为【左根右】10 20 30 40 50 60 70
            // 后序遍历：遍历顺序规则为【左右根】10 30 20 50 70 60 40
            System.out.print(node.value + " ");
            recursiveTraversal(node.left);
            recursiveTraversal(node.right);
        }
    }

    /**
     * 循环遍历
     */
    public void cycleTraversal() {
        Node node = root;
        LinkedList<Node> stack = new LinkedList<>();
        while (node != null || !stack.isEmpty()) {
            if (node != null) {
                stack.push(node);
                // 先序遍历
//                System.out.print(node.value + " ");
                node = node.left;
            } else {
                node = stack.pop();
                // 中序遍历
                System.out.print(node.value + " ");
                node = node.right;
            }
        }
        System.out.println();
    }

    public void mid() {
        Node node = root;
        LinkedList<Node> stack = new LinkedList<>();
        putLeftNode(stack, node);
        while (!stack.isEmpty()) {
            node = stack.poll();
            System.out.print(node.value + " ");
            if (node.right != null) {
                putLeftNode(stack, node.right);
            }
        }
    }

    private void putLeftNode(LinkedList<Node> stack, Node node) {
        while (node != null) {
            stack.push(node);
            node = node.left;
        }
    }

    /**
     * 先序遍历
     */
    public void pre() {
        Node node = root;
        if (node != null) {
            LinkedList<Node> stack = new LinkedList<>();
            stack.push(node);
            while (!stack.isEmpty()) {
                node = stack.pop();
                System.out.print(node.value + " ");
                if (node.right != null) {
                    stack.push(node.right);
                }
                if (node.left != null) {
                    stack.push(node.left);
                }
            }
        }
        System.out.println();
    }

    /**
     * 后序遍历：左右中 == 中右左取反
     */
    public void pos() {
        Node node = root;
        if (node != null) {
            LinkedList<Node> s1 = new LinkedList<>();
            LinkedList<Node> s2 = new LinkedList<>();
            s1.push(node);
            while (!s1.isEmpty()) {
                node = s1.pop();
                s2.push(node);
                if (node.left != null) {
                    s1.push(node.left);
                }
                if (node.right != null) {
                    s1.push(node.right);
                }
            }
            while (!s2.isEmpty()) {
                node = s2.pop();
                System.out.println(node.value + " ");
            }
        }
        System.out.println();
    }

    /** 循环后序遍历 */
    public void cycleTraversalEnd() {
        Node node = root;
        LinkedList<Node> stack = new LinkedList<>();
        while (node != null || !stack.isEmpty()) {
            if (node != null) {
                stack.push(node);
                node = node.left;
            } else {
                node = stack.pop();
                if (node.right == null || node.n == 0) {
                    System.out.print(node.value + " ");
                    node = null;
                } else {
                    node.n = 0;
                    stack.push(node);
                    node = node.right;
                }
            }
        }
    }

    /**
     * 层次遍历
     */
    public void levelTraversal() {
        LinkedList<Node> queue = new LinkedList<>();
		Node last = root;
		Node nlast = null;
        queue.add(root);
        while (!queue.isEmpty()) {
            Node p = queue.removeFirst();
            System.out.print(p.value + " ");
            if (p.left != null) {
                queue.addLast(p.left);
				nlast = p.left;
            }
            if (p.right != null) {
                queue.addLast(p.right);
				nlast = p.right;
            }
			if (p.value.equals(last.value)) {
				System.out.println();
				last = nlast;
			}
        }
    }

    public static void main(String[] args) {
        BinarySearchTree<Integer> test = new BinarySearchTree<>();
        test.put(40);
        test.put(20);
        test.put(30);
        test.put(10);
        test.put(60);
        test.put(50);
        test.put(70);

        test.cycleTraversalEnd();
        System.out.println();
        test.cycleTraversal();
        test.mid();
        System.out.println();
        test.recursiveTraversal();
		System.out.println();

		test.put(25);
		test.put(27);
		test.put(22);
        test.put(23);
        test.levelTraversal();

		test.delete(20);
		test.levelTraversal();
    }

}
